An Access Control List (ACL) includes a plurality of Filtering Rules (FRs) for packet classification. The FRs are used in firewalls implemented within a router and are used to determine an action to be performed with regard to a received packet based on the classification. Information from the packet's header is compared against the FRs in order to determine if the packet falls within the scope of one or more of the FRs.
Each filtering rule or filter may include one or more of the fields listed in Table I, and the rules specify how each field should be mapped or compared with the packet header. Typically, the source/destination IP address is specified by a prefix/mask of the packet, and the source/destination port numbers are specified by a range. A given packet can match several of the filters in the database, so each filter is given a cost, and the action dictated by the least cost matching filter is applied, in one example.
For instance, upon receipt of a packet, the packet may be compared to the ACL and an action such as permit, deny, count, redirect or log may be performed as to the packet. Fields from the packets used typically include the source IP address, the destination IP address, layer four protocol, source and destination ports, and possibly some other miscellaneous packet properties. Examples of these fields and sizes are shown in Table 1.
TABLE 1Fields and sizes often used in thefiltering rules in an ACL for classificationFieldSize (bits)CommentType/protocol4-8Such as IP, UDP etc . . .Source IP address32Destination IP address32Source Port Number16Destination Port Number16Misc.4-8Such as established, echo . . .Total104-108
Usually, rules contained within an ACL are presented in a list, a sample of which is shown below:                permit tcp any any established        permit udp 10.35.0.0/16 10.50.6.128/26 ranges snmp snmptrap        deny tcp 10.21.133.0/24 31.50.138.141 eq 3306        
Based on sample, conventional ACL lists provided by industry, ACL lists have ranged from a few entries (tens of rules) to a few thousands of filtering rules, as shown in Table 2.
TABLE 2Example of sizes of ACLsSourceSize (entries)CommentAOL2814Particularly long exampleUCR361Problematic for memory in methods like RFCand HiCutsMFN140153TypicalMFN112114TypicalEBORN833Short list
The most used format for an ACL list is that given by Cisco Systems, in which the rules are given in a linear list, and the first matching rule is applied to a received packet. In this example, the ordering number in the list is used as the implicit filter cost.
Simplest hardware implementations use ternary CAMs (content addressable memory). Rules are stored in the CAM array in the order of decreased priority. Simple and flexible, ternary CAMs are fairly expensive and power hungry. However, 64K×128 ternary CAMs may be available.
Recursive Flow Classification (RFC), as described in “Packet Classification on Multiple Fields,” Proceedings of Sigcomm, Computer Communication Review, Vol. 29, No. 4, pages 147-160, September 1999, by P. Gupta and N. McKeown, is another hardware mappable method, believed to be used in existing implementations, including by Cisco Systems and Lucent Technologies. See also T. V. Lakshman and D. Stidialis, “High Speed Policy-based Packet Forwarding Using Efficient Multidimensional Range Matching,” Proceedings of ACM Sigcomm 98, October 1998. It is also known as equivalenced cross-producing. The method can be pipelined, and lends it self to an efficient hardware implementation using considerable memory, typically implemented in DRAM. However, without pushing the technology envelope, classifiers with thousands of rules can be implemented and achieve OC192 rates for 40 Byte packets. In this method, all fields of the packet header is split up into multiple chunks, which are used to index into multiple memories. The contents of each memory is precomputed so as to compress regions that could fall into similar rule sets. Recursive recombination of the results and subsequent lookups finally yields the best matching rule.
A number of hash methods exist, such as the Tuple Space Search, described in V. Srinivasan, S. Suri and G. Vargese, “Packet Classification using Tuple Space Search”, Proceedings of ACM Sigcomm, pages 135-146, September 1999. In this example, rules have to be initially partitioned into bins which uniquely identifies lengths of prefix specified in each dimension of the rule, and each of these bins are subsequently hashed. An analysis of the available ACL lists indicated that the number of bins are relatively large, and since each bin needs be searched and the results combined, there would not be considerable improvement over a linear search.
Another technique uses a grid of tries, as described in V. Srinivasan, S. Suri, G. Vargese and M. Valdvogel, “Fast Scalable Level Four Switching,” Proceedings of SIGCOMM 98, pages 203-214, September 1998. In this example, a method generalizes the standard one dimensional trie search solution to two dimensions. Further work, described in L. Qiu, S. Suri, G. Vargese, “Fast Firewall Implementations for Software and Hardware-based Routers,” Technical Report MSR-TR-2001-61, www.research.microsoft.com, showed how to extend a trie search to multiple dimensions, and to apply pruning, compression and selective duplication to balance the memory and throughput constraints. Unfortunately, backtracking may be difficult to implement in a forwarding engine.
Also, a method exists called Hierarchical Intelligent Cuttings (HiCuts) is described in Pankaj Gupta and Nick McKeown, “Packet Classification using Hierarchical Intelligent Cuttings,” IEEE Micro, pages 34-41, Vol. 21, No. 1, January/February 2000. HiCuts is a tree based approach that partitions the multi-dimensional search space guided by heuristics. Each end node of the tree stores a small number of rules that are then sequentially searched to find the best match. Associated with each internal node is a cut defined as a number of equal size interval that a particular dimension is partitioned into, and this is performed recursively on the child nodes at each level.
It is also possible to recast classification as a problem in computational geometry, such as the “point location”, “ray tracing” or “rectangle enclosure” problem. An example is described in F. Preparata and M. I. Shamos, “Computational Geometry: an Introduction,” Springer-Verlag, 1985. For non-overlapping regions multiple dimensions, there are results that allow trade-off of query time with storage. Unfortunately, none of these methods perform well for both storage requirements and query time, nor can these results be easily generalized to the case of overlapping regions which is the case for ACL classification.
Accordingly, as recognized by the present inventor, what is needed is a method for performing a lookup of a packet against an access control list that is memory efficient. It is against this background that various embodiments of the present invention were developed.